Биномиальные коэффициенты и эквивалентность определений

$\binom{n}{k}$ есть число $k$-элементных подмножеств $n$-элементного множества

$\binom{n}{k}$ есть коэффициент при $x^k y^{n-k}$ многочлена $(x+y)^n$

$\binom{n}{k} = \Delta(n, k)$, где $\Delta(n, k)$ задана рекуррентным соотношением: $$\Delta(n, k) = \Delta(n - 1, k - 1) + \Delta(n - 1, k)$$ $$\Delta(n, 0) = \Delta(n, n) = 1$$

Определения 1, 2 и 3 биномиального коэффициента $\binom{n}{k}$ эквивалентны.

** 1. Эквивалентность 1 и 2:** Перемножив $n$ скобок $(x+y)(x+y)\dots(x+y)$, получим сумму одночленов. Одночлен $x^k y^{n-k}$ получится, если из $k$ скобок выбрать $x$, а из остальных — $y$. Коэффициент при $x^k y^{n-k}$ равен числу способов выбрать $k$ скобок из $n$. Следовательно, Определение 2 задает $\binom{n}{k}$. ** 2. Эквивалентность 1 и 3:** Проверим граничные условия: $$\binom{n}{0} = 1 \text{ (пустое подмножество)}\mathpunct{,}~~ \binom{n}{n} = 1 \text{ (само множество)}$$ $k$-элементные подмножества разобьем на 2 группы: содержащие $n$-й элемент и не содержащие $n$-й элемент. Число первых равно $\binom{n-1}{k-1}$, число вторых равно $\binom{n-1}{k}$. Получаем: $$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$ Таким образом, $\binom{n}{k} = \Delta(n, k)$, т.е. определение 3 задает $\binom{n}{k}$. $\square$